package arithmetic2.day10;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;

/*
    并行计算数组中孤岛的个数:
        将数组分为上下两份
 */
public class Islet02 {
    public static void main(String[] args) {
        int arr[][] = {
                {0, 0, 1, 0, 1, 0, 0},
                {1, 1, 1, 0, 1, 0, 0},
                {1, 0, 0, 0, 1, 0, 0},
                {1, 0, 0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0, 0, 0}
        };
        System.out.println("res:"+islet(arr));
    }

    public static int islet(int arr[][]) {
        int res = 0;
        //将数组分为上下两份
        int n = arr.length;
        int nMid = n >> 1;
        int m = arr[0].length;
        //定义两个数组用来存储两个小数组边界上的2是由那个点感染的，用x:y形式拼接为字符串
        String temp1[] = new String[m];
        String temp2[] = new String[m];
        //模拟两个cpu并行计算
        CompletableFuture<Integer> future1 = CompletableFuture.supplyAsync(() -> {
            int res1 = 0;
            for (int i = 0; i <= nMid; i++) {
                for (int j = 0; j < m; j++) {
                    if (arr[i][j] == 1) {
                        res1++;
                        infect(arr, i, j, 0, nMid + 1, m, i + ":" + j, temp1, temp2);
                    }
                }
            }
            return res1;
        });
        CompletableFuture<Integer> future2 = CompletableFuture.supplyAsync(() -> {
            int res2 = 0;
            for (int i = nMid + 1; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (arr[i][j] == 1) {
                        res2++;
                        infect(arr, i, j, nMid + 1, n, m, i + ":" + j, temp1, temp2);
                    }
                }
            }
            return res2;
        });
        try {
            System.out.println("res1:"+future1.get());
            System.out.println("res2:"+future2.get());
            res = future1.get() + future2.get();
            //创建一个并查集,将当前感染源全部加入到并查集中
            List<String> list = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                if (temp1[i] != null) {
                    list.add(temp1[i]);
                }
                if (temp2[i] != null) {
                    list.add(temp2[i]);
                }
            }
            UnionFind<String> unionFind = new UnionFind<>(list);
            //使用并查集将两个结果合并
            for (int i = 0; i < m; i++) {
                if (temp1[i] != null && temp2[i] != null) {
                    //如果两个感染源不是一个，合并两个感染源,res-1
                    if (!unionFind.isSameSet(temp1[i], temp2[i])) {
                        unionFind.union(temp1[i], temp2[i]);
                        res -= 1;
                    }
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
        return res;
    }

    /**
     * @param arr
     * @param i
     * @param j
     * @param n:x轴的下边界
     * @param t:x轴的上边界
     * @param m:y轴的上边界,下边界默认为0
     */
    public static void infect(int arr[][], int i, int j, int n, int t, int m, String origin, String temp1[], String temp2[]) {
        if (i < n || i >= t || j < 0 || j >= m || arr[i][j] != 1) {
            return;
        }
        arr[i][j] = 2;
        if (i == arr.length / 2) {
            temp1[j] = origin;
        }
        if (i == arr.length / 2 + 1) {
            temp2[j] = origin;
        }
        infect(arr, i - 1, j, n, t, m, origin, temp1, temp2);
        infect(arr, i, j + 1, n, t, m, origin, temp1, temp2);
        infect(arr, i + 1, j, n, t, m, origin, temp1, temp2);
        infect(arr, i, j - 1, n, t, m, origin, temp1, temp2);
    }
}
